home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 4 / Info_Mac IV CD-ROM (Pacific HiTech Inc.)(August 1994).iso / Development / Source / RegionToRectangles Folder / README < prev    next >
Encoding:
Text File  |  1994-02-19  |  4.4 KB  |  120 lines  |  [TEXT/EDIT]
  1.  
  2.  
  3. This is a C function that splits a region into its constituent
  4. rectangles for processing, plus a sample program to demonstrate it
  5. in action. If you are interested in this sort of thing, or already
  6. have such code and want to compare implementations, read on.
  7.  
  8. You should have:
  9.  
  10.     README: you're reading it.
  11.  
  12.     EachRegionRect.c:    the actual function
  13.  
  14.     RegionToRectangles.c:    the demonstration program source code
  15.  
  16.     RegionToRectangles:    compiled demonstration program
  17.  
  18. I wrote this code just to see if I could figure out how regions
  19. worked rather than from any particular need. This meant that the
  20. straightforward approach - disassembling the Toolbox - was not on.
  21. What would be the fun in that? Bear with me through a somewhat
  22. rambling design process, or just look at the actual code if
  23. impatient.
  24.  
  25. First, I wrote a little program to create various regions and did
  26. some poking around with the data structure. For those who haven't
  27. tried this, Quickdraw regions are stored as a list of horizontal
  28. edges. For instance, a H shape would look like:
  29.  
  30.  
  31.     ----    ----
  32.  
  33.         ----
  34.  
  35.         ----
  36.  
  37.     ----    ----
  38.  
  39.  
  40. The actual data is divided into scan lines, each of which has a Y
  41. value, one or more X1 X2 pairs, and is terminated by 32767. The
  42. region ends with a scan line with Y value 32767. Continuing with
  43. the H example, the data looks like
  44.  
  45.      0     0 32    64 96    32767
  46.     32    32 64    32767
  47.     64    32 64    32767
  48.     96     0 32    64 96    32767
  49.     32767
  50.  
  51. Next I tried to get some idea of how to go about it in the good
  52. book: "Computer Graphics Principles and Practice." This has a
  53. chapter on Shapes, which are just regions under a new name but
  54. implemented differently. A further reference, "How to Color in a
  55. Coloring Book" by Henry Lieberman, turned out to be a seed filling
  56. (paint bucket) algorithmn but dealt with similar data.
  57.  
  58. After some false starts, a reasonable algorithmn seemed to be
  59. this:
  60.  
  61. * Begin a list of top edges for rectangles. The X pairs in the
  62. first scan line will all qualify.
  63.  
  64. * Each subsequent X pair on a scan line is compared to the top
  65. edges on this list.
  66.  
  67. * If it overlaps (ie is underneath) we have a matching bottom
  68. edge. Process the rectangle and remove the top from the list.
  69.  
  70. * If it doesn't overlap, it is a new top edge. Add to the list.
  71.  
  72. * A partial overlap is processed by splitting one or both edges
  73. into pieces, and applying the overlap test to each individual
  74. segment.
  75.  
  76. At this point I was ready to start coding, and spent a couple of
  77. hours thinking about how to maintain this list of Y X1 X2 edges.The
  78. special case of a partial overlap looked like a real pain: the
  79. code would need to be able to delete an existing edge and replace
  80. it with two new ones.
  81.  
  82. It then occurred to me that all these edges are just run length
  83. encodings of Y, so why not "uncompress" them? No two edges can
  84. share the same X value: if they did they would be overlapping and
  85. by the algorithmn would have to be processed and split until they
  86. didn't. So, all I really needed was an array to store the Y value
  87. for each possible X. Most regions are not going to be bigger than
  88. the screen, and even a giant monitor is 1024 pixels = only 2K of
  89. memory. I therefore decided to use a local array that stores a top
  90. edge for every pixel, with heap allocation in emergencies.
  91.  
  92. NOTES:
  93.  
  94. Macs with 68000 processors have an 8K stack by default and those
  95. with 68020 or better 24K. A 2K local array won't make much of a
  96. dent, but you could reduce the #define StackMax value if you are
  97. worried about the smaller machines.
  98.  
  99. The code is (obviously) in C, because that's the language I've
  100. been working with lately. I can't see any reason why it couldn't
  101. be in Pascal if you prefer, although the switch between stack and
  102. heap storage would be messier. An assembly language implementation
  103. could be really neat: minimum stack usage, etc.
  104.  
  105. This particular program was developed under THINK C version 5, and
  106. moved unchanged to version 6.
  107.  
  108. The code uses an index to step through the region data rather than
  109. a pointer. This is because Quickdraw allocates regions itself
  110. rather than through the Memory Manager and there doesn't seem to
  111. be any way to lock them.
  112.  
  113. There is an aesthetic problem with this code if used for screen
  114. updates. The rectangles are processed in Y-X order on the _bottom_
  115. edges, which as the demo program will show looks a bit peculiar.
  116. For screen updating you should use the code to build a list of
  117. rectangles, then sort them by top edge before drawing. This, as
  118. the textbooks say, is left as an exercise for the reader.
  119.  
  120.